#include <bits/stdc++.h>

using namespace std;

// 删掉1个数字后长度为k的子数组最大累加和
// 给定一个数组nums，求必须删除一个数字后的新数组中
// 长度为k的子数组最大累加和，删除哪个数字随意
// 对数器验证

// 暴力方法
// 为了测试
// 删掉index位置的元素，然后返回新数组
vector<int> del(vector<int> &nums, int index)
{
    int len = nums.size() - 1;
    vector<int> ans(len);
    int i = 0;
    for (int j = 0; j < nums.size(); ++j)
    {
        if (j != index) ans[i++] = nums[j];
    }
    return ans;
}

// 暴力方法
// 为了测试
// 枚举每一个子数组找到最大累加和
int lenKmaxSum(vector<int> &nums, int k)
{
    int n = nums.size();
    int ans = INT_MIN;
    for (int i = 0; i <= n - k; i++)
    {
        int cur = 0;
        for (int j = i, cnt = 0; cnt < k; j++, cnt++)
        {
            cur += nums[j];
        }
        ans = max(ans, cur);
    }
    return ans;
}

// 暴力方法
// 为了测试
int maxSum1(vector<int> &nums, int k)
{
    int n = nums.size();
    if (n <= k) return 0;
    int ans = INT_MIN;
    for (int i = 0; i < n; ++i)
    {
        vector<int> &&rest = del(nums, i);
        ans = max(ans, lenKmaxSum(rest, k));
    }
    return ans;
}

// 正式方法
// 时间复杂度O(N)
int maxSum2(vector<int> &nums, int k)
{
    int n = nums.size();
    if (n <= k) return 0;
    // 单调队列 : 维持窗口内最小值的更新结构，讲解054的内容
    int window[n];
    memset(window, 0, sizeof window);
    int l = 0, r = 0;
    // 窗口累加和
    long sum = 0;
    int ans = INT_MIN; // ans = max(长度为k+1的窗口中的数字之后 - 窗口内的最小值)
    for (int i = 0; i < n; ++i)
    {
        // 单调队列 : i位置进入单调队列
        while (l < r && nums[window[r - 1]] > nums[i]) --r;
        window[r++] = i;
        sum += nums[i];
        if (i >= k)
        {
            ans = max(ans, (int)(sum - nums[window[l]]));
            // 单调队列 : 如果单调队列最左侧的位置过期了，从队列中弹出
            if (window[l] + k == i) ++l;
            sum -= nums[i - k];
        }
    }

    return ans;
}

// 为了测试
// 生成长度为n，值在[-v, +v]之间的随机数组
vector<int> randomArray(int n, int v)
{
    vector<int> arr(n);
    for (int i = 0; i < n; ++i)
    {
        arr[i] = rand() % (2 * v + 1) - v;
    }
    return arr;
}

// 为了测试
// 对数器
int main()
{
    srand(time(nullptr));
    int n = 200;
    int v = 1000;
    int testTime = 10000;
    cout << "测试开始" << endl;
    for (int i = 0; i < testTime; i++)
    {
        int len = rand() % n;
        vector<int>&& nums = randomArray(len, v);
        int k = rand() % n + 1;
        int ans1 = maxSum1(nums, k);
        int ans2 = maxSum1(nums, k);
        if (ans1 != ans2)
        {
            cout << "出错了!" << endl;
        }
    }
    cout << "测试结束" << endl;

    return 0;
}